package leetcode.day_2020_2021_2_1_2021_2_7;

import java.util.Arrays;

/**
 * 16. 最接近的三数之和
 * https://book.douban.com/subject/30246992/
 */
public class LeetCode0016 {
    public static void main(String[] args) {
        System.out.println(threeSumClosest(new int[]{-1, 2, 1, -4}, 1));
        System.out.println(threeSumClosest(new int[]{1, 1, 1, 0}, -100));

    }

    // 双指针法
    public static int threeSumClosest2(int[] nums, int target) {
        Arrays.sort(nums);
        int result = 0;
        int res = Integer.MAX_VALUE;
        for(int i=0; i<nums.length; i++) {
            int demoTarget = nums[i] - target;
            int left = 0, right = nums.length-1;
            while (left < right) {
                if(i == left) {
                    left++;
                } else if(i == right) {
                    right--;
                } else {
                    int demo = Math.abs(nums[left] + nums[right] + demoTarget);
                    if (res > demo) {
                        result = nums[i]+nums[left]+nums[right];
                        res = demo;
                    }
                }
            }
        }
        return result;
    }

    // 暴力法
    public static int threeSumClosest(int[] nums, int target) {
        int res = Integer.MAX_VALUE; // 用来存储差值
        int result = 0; // 用来存储符合条件的最终值
        for(int i=0; i<nums.length; i++) {
            for(int j=i+1; j<nums.length; j++) {
                for(int k=j+1; k<nums.length; k++) {
                    int demo = Math.abs(nums[i]+nums[j]+nums[k]-target);
                    if (res > demo) {
                        result = nums[i]+nums[j]+nums[k];
                        res = demo;
                    }
                }
            }
        }
        return result;
    }
}
